%%% Hlavní soubor. Zde se definují základní parametry a odkazuje se na ostatní části. %%%

%% Verze pro jednostranný tisk:
% Okraje: levý 40mm, pravý 25mm, horní a dolní 25mm
% (ale pozor, LaTeX si sám přidává 1in)
\documentclass[12pt,a4paper]{report}
\setlength\textwidth{145mm}
\setlength\textheight{247mm}
\setlength\oddsidemargin{15mm}
\setlength\evensidemargin{15mm}
\setlength\topmargin{0mm}
\setlength\headsep{0mm}
\setlength\headheight{0mm}
% \openright zařídí, aby následující text začínal na pravé straně knihy
\let\openright=\clearpage

%% Pokud tiskneme oboustranně:
% \documentclass[12pt,a4paper,twoside,openright]{report}
% \setlength\textwidth{145mm}
% \setlength\textheight{247mm}
% \setlength\oddsidemargin{15mm}
% \setlength\evensidemargin{0mm}
% \setlength\topmargin{0mm}
% \setlength\headsep{0mm}
% \setlength\headheight{0mm}
% \let\openright=\cleardoublepage

%% Použité kódování znaků: obvykle latin2, cp1250 nebo utf8:
\usepackage[utf8]{inputenc}

%% Ostatní balíčky
\usepackage{graphicx}
\usepackage{wrapfig}	% figures wrapped around by text
\usepackage{subfig}		% subfigures
\usepackage{paralist}	% list in a paragraph
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{longtable}	% tables on multiple pages

%% algoritmy
\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{listings}  % displaying source code

%% Balíček hyperref, kterým jdou vyrábět klikací odkazy v PDF,
%% ale hlavně ho používáme k uložení metadat do PDF (včetně obsahu).
%% POZOR, nezapomeňte vyplnit jméno práce a autora.
\usepackage[ps2pdf,unicode]{hyperref}   % Musí být za všemi ostatními balíčky
\hypersetup{pdftitle=Planning systems in game level design and agent control}
\hypersetup{pdfauthor=Csaba Tóth}

%%% Drobné úpravy stylu

% Tato makra přesvědčují mírně ošklivým trikem LaTeX, aby hlavičky kapitol
% sázel příčetněji a nevynechával nad nimi spoustu místa. Směle ignorujte.
\makeatletter
\def\@makechapterhead#1{
  {\parindent \z@ \raggedright \normalfont
   \Huge\bfseries \thechapter. #1
   \par\nobreak
   \vskip 20\p@
}}
\def\@makeschapterhead#1{
  {\parindent \z@ \raggedright \normalfont
   \Huge\bfseries #1
   \par\nobreak
   \vskip 20\p@
}}
\makeatother

% Toto makro definuje kapitolu, která není očíslovaná, ale je uvedena v obsahu.
\def\chapwithtoc#1{
\chapter*{#1}
\addcontentsline{toc}{chapter}{#1}
}

\begin{document}

% Trochu volnější nastavení dělení slov, než je default.
\lefthyphenmin=2
\righthyphenmin=2

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Titulní strana práce

\pagestyle{empty}
\begin{center}

\large

Charles University in Prague

\medskip

Faculty of Mathematics and Physics

\vfill

{\bf\Large MASTER THESIS}

\vfill

\centerline{\mbox{\includegraphics[width=60mm]{../img/logo.eps}}}

\vfill
\vspace{5mm}

{\LARGE Csaba Tóth}

\vspace{15mm}

% Název práce přesně podle zadání
{\LARGE\bfseries Planning systems in game level design and agent control}

\vfill

% Název katedry nebo ústavu, kde byla práce oficiálně zadána
% (dle Organizační struktury MFF UK)
Department of Software and Computer Science Education

\vfill

\begin{tabular}{rl}

Supervisor of the master thesis: & Mgr. Rudolf Kadlec \\
\noalign{\vspace{2mm}}
Study programme: & Informatics \\
\noalign{\vspace{2mm}}
Specialization: & Software Systems \\
\end{tabular}

\vfill

% Zde doplňte rok
Prague 2012

\end{center}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Následuje vevázaný list -- kopie podepsaného "Zadání diplomové práce".
%%% Toto zadání NENÍ součástí elektronické verze práce, nescanovat.

%%% Na tomto místě mohou být napsána případná poděkování (vedoucímu práce,
%%% konzultantovi, tomu, kdo zapůjčil software, literaturu apod.)

\openright

\noindent
%Dedication.
I would like to thank to my supervisor Rudolf Kadlec for his always available guidance during the preparation of the thesis. I would also thank to my family and close friends whose advices greatly assisted my work. Finally I would like to thank my testers who were kind enough to try my game.


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Strana s čestným prohlášením k diplomové práci

\vglue 0pt plus 1fill

\noindent
I declare that I carried out this master thesis independently, and only with the cited
sources, literature and other professional sources.

\medskip\noindent
I understand that my work relates to the rights and obligations under the Act No.
121/2000 Coll., the Copyright Act, as amended, in particular the fact that the Charles
University in Prague has the right to conclude a license agreement on the use of this
work as a school work pursuant to Section 60 paragraph 1 of the Copyright Act.

\vspace{10mm}

\hbox{\hbox to 0.5\hsize{%
%In Prague, 13 April, 2012
............%In ........ date ............
\hss}\hbox to 0.5\hsize{%
%Csaba Tóth
signature of the author
\hss}}

\vspace{20mm}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Povinná informační strana diplomové práce

\vbox to 0.5\vsize{
\setlength\parindent{0mm}
\setlength\parskip{2.5mm}	% 5mm

Název práce:
Plánování v designu herních úrovní a řízení agentů
% přesně dle zadání

Autor:
Csaba Tóth

Katedra:  % Případně Ústav:
Kabinet software a výuky informatiky
% dle Organizační struktury MFF UK

Vedoucí diplomové práce:
Mgr. Rudolf Kadlec, Kabinet software a výuky informatiky
% dle Organizační struktury MFF UK, případně plný název pracoviště mimo MFF UK

Abstrakt:
Plánovacie systémy sú vyspelé nástroje výpočtovej techniky, ale ich využitie v počítačových hrách je zatiaľ obmedzené. Rozhodli sme sa vytvoriť hru, ktorá je založená na týchto nástrojoch. Ak sa nám podarí dokázať, že voľne dostupné, obecné plánovače sú vhodnými náhradami špeciálnych riešení moderných hier, ukázali by sme nový smer malým vývojovým firmám a popularizovali nový typ hry, ktorý je riadený plánovačom. 
Pokúsili sme použiť plánovače v dvoch úlohách: vo vývoji, na čiastočnú automatizáciu designu levelov a počas skutočnej hry, vo vytváraní správania sa agentov.
Náš program je hlavolam, kde má hráč za úlohu odhaľovať plány a zámery všetkých agentov, spoznať nebezpečia, a použitím získanej znalosti 
potom upraviť herný svet tak, aby donútil agentov k dosiahnutiu požadoného výsledku.
Ďalšou súčasťou programu je generátor herných levelov.
Dospeli sme k záveru, že určitými ohraničeniami dokážeme plánovač využiť vo vytváraní vierohodného správania sa agentov. Napriek tomu, že určité rozhodnutia plánovač nedokáže za nás vykonať, uľahčí prácu designera herných levelov.


%Rolou virtuálnych agentov v počítačových hrách je naplniť virtuálny svet obyvateľmi. Vymysleli sme hru, kde agenti reprezentujú nočných strážcov múzea a jedného zlodeja. Úlohou hráča je odhaľovať plány a zámery všetkých agentov, potom zlodejom pomáhať, a strážcom prekážať v plnení ich zámerov. Použitie externého plánovača poskytuje dve zaujímavé možnosti v level designu a v riadení agentov.
%Skúmali sme realitu čiastočne automatizovaného designu levelov. To znamená, že level sa generuje zo zadanej mapy a s požadovanou obtiažnosťou. Z tohto vstupu vznikajú hlavolamy pre hráča. Tento prístup urýchli vývoj, alebo zvýši znovuhrateľnost hry, alebo obidve možnosti naraz.
%Počas skutočnej hry plánovač sme využili vo vytváraní vierohodného správania sa agentov.
%Cieľom práce bolo vytvoriť prototyp hry, ktorá je založená na plánovačoch. Súčasťou programu sú ukážkové levely, pričom naviac nám poskytuje možnosť vytvárania ďalších levelov.

%Jednou z rolí virtuálnych agentov v počítačových hrách je naplniť virtuálny svet obyvateľmi. Cieľom práce bolo vytvoriť prototyp hry, v ktorom tieto dva typy agentov sú riadení externým plánovač algoritmom. V našom prípade agenti reprezentujú nočných strážcov múzea a jedného zlodeja. Úlohou hráča je odhaľovať plány a zámery všetkých agentov, zlodejom pomáhať, a strážcom prekážať v ich splnení.
%Externý plánovač tretej strany bol použitý dvoma spôsobmi:
%Po prvé, v práci sú skúmané možnosti čiastočne automatizovaného dizajnu levelov tohto typu hry pomocou plánovacích nástrojov. To znamená, že level sa generuje zo zadanej mapy a požadovanej obtiažnosti. Z tohto vstupu vznikajú konkrétni strážcovia, alarmy a ich rozmiestnenie, ktoré spolu s mapou tvoria herný level.
%Po druhé, počas skutočnej hry je plánovač využitý vo vytvorení vierohodného správania sa agentov.
%Dôraz je kladený na integrácii plánovača do rozhodovacích mechanizmov agenta, a nie na grafické rozhranie, ani na editačné nástroje. 
%Súčasťou práce je implementácia prototypu hry s ukážkovými levelmi, ktorá zároveň umožňuje vytváranie ďalších levelov.

% abstrakt v rozsahu 80-200 slov; nejedná se však o opis zadání diplomové práce

Klíčová slova:
% 3 až 5 klíčových slov
plánovanie, hra, level dizajn, umelá bytosť, uveriteľné správanie


\vss}\nobreak\vbox to 0.49\vsize{
\setlength\parindent{0mm}
\setlength\parskip{2.5mm}	% 5mm

Title:
Planning systems in game level design and agent control
% přesný překlad názvu práce v angličtině

Author:
Csaba Tóth

Department:
Department of Software and Computer Science Education
% dle Organizační struktury MFF UK v angličtině

Supervisor:
Mgr. Rudolf Kadlec, Department of Software and Computer Science Education
% dle Organizační struktury MFF UK, případně plný název pracoviště
% mimo MFF UK v angličtině

Abstract:
Planners are well developed tools in computer science, but their role is rather limited in games. We decided to test the possibilities of writing such a game around them. Proving that freely available, general purpose planning systems are worthy alternatives to custom made solutions could open a new path to small developers and popularize a new kind of gameplay powered by these tools.
We attempted to exploit planners in two roles, in the development, to partially automate the level design process; and in the gameplay as a decision making tool for the acting agents. 
Our program is a puzzle game, more precisely an anticipation game, where the player has to foresee the future actions of the acting agents, then discover the pitfalls where they are heading. Using this knowledge he can modify their environment and force them to a desired outcome.
A part of our program is a generator of such game challenges.
We came to a conclusion that within some limitations planners are capable of creating believable agent behavior and while not all decisions can be handed over to the planning systems, they can lighten the task of the level designer.


%In computer games virtual agents fulfill the role of inhabitants of the game world. We took a game idea, where these agents represent the night watch of a museum and an intruding thief. The goal of the player is to find out what the agents are up to, then help the burglar, while preventing the guards in the execution of their plans. Using external planners in such a game seemed to be interesting in two perspectives: In level design, and in the gameplay itself.
%We studied the possibilities of partially automating the level design. This means that the game level is generated using a map file and the required difficulty. The program uses these inputs to generate player challenges, and with that shortens development time, and/or increases the replay value of the final product.
%Through the gameplay itself were utilized in agent behavior to emulate rational, and flexible decision making.
%The aim of our work was to create a game prototype (somewhat lacking in graphics) with planners as a fundamental concept.

% abstrakt v rozsahu 80-200 slov v angličtině; nejedná se však o překlad
% zadání diplomové práce

Keywords:
planning, game, level design, artificial being, believable behavior
% 3 až 5 klíčových slov v angličtině

\vss}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Strana s automaticky generovaným obsahem diplomové práce. U matematických
%%% prací je přípustné, aby seznam tabulek a zkratek, existují-li, byl umístěn
%%% na začátku práce, místo na jejím konci.

\openright
\pagestyle{plain}
\setcounter{page}{1}
\tableofcontents

%%% Jednotlivé kapitoly práce jsou pro přehlednost uloženy v samostatných souborech
\include{preface}
\include{game_world}
\include{gameplay}
\include{problem_definition}
\include{agent_control}
\include{creating_levels}
\include{implementation}
\include{planners}
\include{player_responses}

% Ukázka použití některých konstrukcí LateXu (odkomentujte, chcete-li)
% \include{example}

\include{epilog}

%%% Seznam použité literatury
\include{bibliography}

%%% Tabulky v diplomové práci, existují-li.
\chapwithtoc{List of Tables}

\begin{description}
  \item[table~\ref{tab:test1}] Planner results of test series 1
  \item[table~\ref{tab:test2}] Planner results of test series 2
  \item[table~\ref{tab:test4}] Planner results of test series 4
\end{description}


%%% Použité zkratky v diplomové práci, existují-li, včetně jejich vysvětlení.
%\chapwithtoc{List of Abbreviations}
\include{list_of_abbreviations}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Přílohy k diplomové práci, existují-li (různé dodatky jako výpisy programů,
%%% diagramy apod.). Každá příloha musí být alespoň jednou odkazována z vlastního
%%% textu práce. Přílohy se číslují.
\include{attachments}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\openright
\end{document}
